package cn.whdream.datastructure.binarysorttree;

/**
 * 
 * @author admin 二叉排序树 自己的思路的版本
 * TODO 有空可以对比下，老师的版本的和自己版本的优劣对比
 */
public class BinarySortTreeDemoForStudent {
	public static void main(String[] args) {
		int[] arr = {7, 3, 10, 12, 5, 1, 9, 2,11};
		BinaryTree tree = new BinaryTree();
		for (int i : arr) {
			tree.add(new Node(i));
		}
		tree.infixOrder();
		Node del;
		/**
		 * 注意，本版本不支持多个结点的删除；由于parent是方法添加时设置的，结构改变后；parent是不对的！！！！！
		 */
		del = tree.del(10);
		System.out.println("del:"+del);
		tree.infixOrder();
	}

	private static class BinaryTree {
		Node root;

		public void add(Node node) {
			if (root == null) {
				root = node;
				return;
			}
			root.add(node);
		}

		public Node del(int i) {
			if (root == null) {
				return null;
			}
			return root.delNode(i);
		}

		public void infixOrder() {
			if (root != null) {
				root.infixOrder();
			}
		}
	}

	private static class Node {
		int value;
		Node left;
		Node right;
		Node parent;

		public Node(int value, Node left, Node right) {
			super();
			this.value = value;
			this.left = left;
			this.right = right;
		}

		public Node(int value) {
			super();
			this.value = value;
		}

		public Node() {
			super();
		}

		public void add(Node node) {
			if (node == null) {
				return;
			}
			// 小的放到左边，大的放到右边
			if (this.value > node.value) {
				if (this.left == null) {
					this.left = node;
					this.left.parent = this;
				} else {
					this.left.add(node);
				}
			} else {
				if (this.right == null) {
					this.right = node;
					this.right.parent = this;
				} else {
					this.right.add(node);
				}
			}
		}

		/**
		 * 叶子结点 直接删除 非叶子结点，直接删除该子数
		 * 
		 * @param no2 指定的结点号
		 */
		public Node delNode(int no2) {
			Node result = null;
			if (this.value == no2) {
				result = this;
				// 处理叶子结点
				if (isLeafNode()) {
					if (isParentLeftNode()) {
						parent.left = null;
					} else {// 由于是二叉树，所有只考虑左右
						parent.right = null;
					}
					System.out.println("result "+result);
					return result;
				}
				// 处理单孩子结点
				if (isSingleChildTree()) {
					System.out.println("isSingleChildTree");
					if (isParentLeftNode()) {
						if (hasLeftNode()) {
							parent.left = this.left;
						}
						if (hasRightNode()) {
							parent.left = this.right;
						}
					}
					if (isParentRightNode()) {
						if (hasLeftNode()) {
							parent.left = this.left;
						}
						if (hasRightNode()) {
							parent.left = this.right;
						}
					}
				}
				//处理两个孩子的情况
				if(isFullChildTree()) {
					Integer minValue = findRightTreeMinNodeValue();
					//将原来的叶子节点的最小数字删除掉
					result = delNode(minValue);
					result.value = this.value;
					//重新转换为新的结点
					this.value = minValue;
				}

			} else if (this.value > no2) {
				return this.left.delNode(no2);
			} else {
				return this.right.delNode(no2);
			}

			return result;
		}
		/**
		 * 
		 * @return 目前验证了两个都是通过的，不过不是最简单的，下方展示老师的写法
		 */
		private Integer findRightTreeMinNodeValue() {
			if (this.isLeafNode()) {
				return this.value;
			}
			Node temp = null;
			if (hasLeftNode()) {
				temp = left;
			}else {
				temp = right;
			}
			if (temp.isLeafNode()) {
				return temp.value;
			}
			if(temp.isSingleChildTree()) {
				if (temp.hasRightNode()) {
					return temp.right.findRightTreeMinNodeValue();
				}else {
					return temp.left.findRightTreeMinNodeValue();
				}
			}
			if (temp.isFullChildTree()) {
				return temp.right.findRightTreeMinNodeValue();
			}
			return null;
		}
		
//		//编写方法: 
//		//1. 返回的 以node 为根结点的二叉排序树的最小结点的值
//		//2. 删除node 为根结点的二叉排序树的最小结点
//		/**
//		 * 
//		 * @param node 传入的结点(当做二叉排序树的根结点)
//		 * @return 返回的 以node 为根结点的二叉排序树的最小结点的值
//		 */
//		public int delRightTreeMin(Node node) {
//			Node target = node;
//			//循环的查找左子节点，就会找到最小值
//			while(target.left != null) {
//				target = target.left;
//			}
//			//这时 target就指向了最小结点
//			//删除最小结点
//			delNode(target.value);
//			return target.value;
//		}
		private boolean isFullChildTree() {
			return hasLeftNode()&&hasRightNode();
		}

		private boolean isSingleChildTree() {
			boolean hasLeft = hasLeftNode();
			boolean hasRight = hasRightNode();
			// 左右结点只有一个有
			boolean onlyOneChild = (hasLeft && !hasRight) || (!hasLeft && hasRight);
			return onlyOneChild;
		}

		private boolean hasRightNode() {
			return right != null;
		}

		private boolean hasLeftNode() {
			return left != null;
		}

		/**
		 * 没有子树的种类
		 */
		private boolean isLeafNode() {
			return left == null && right == null;
		}

		private boolean isParentLeftNode() {
			if (parent != null && parent.left == this) {
				return true;
			}
			return false;
		}

		private boolean isParentRightNode() {
			if (parent != null && parent.right == this) {
				return true;
			}
			return false;
		}

		public void infixOrder() {
			if (left != null) {
				left.infixOrder();
			}
			System.out.println(this);
			if (right != null) {
				right.infixOrder();
			}
		}

		@Override
		public String toString() {
			return "Node [value=" + value + "have Parent:" + (parent != null) + "]";
		}

	}
}
